package leetcode;
/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0107.java
 * @Author : WangRuoyu
 * @Date 2023/10/22 19:50
 */


import util.Tree;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Q0107 {
    static int hight;

    public static int high(TreeNode node, List<List<Integer>> res) {
        if (node == null) {
            return 0;
        }
        int hight = Math.max(high(node.left, res), high(node.right, res)) + 1;
        if (hight > res.size()) {
            res.add(new ArrayList<>());
        }
        return hight;
    }

    public void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null) {
            return;
        }
        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
        int k = hight - depth;
        res.get(k).add(node.val);
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        hight = high(root, res);
        dfs(root, 1, res);
        return res;
    }

    public static void main(String[] args) {
        Q0107 sl = new Q0107();
        String[] tree = {"3", "9", null, null, "20", "15", null, null, "7", null, null};
        TreeNode root = Tree.createTreeByPreorder(tree);
        System.out.println(sl.levelOrderBottom(root));
    }
}